# 587 困难：安装栅栏

import functools


# def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
def outerTrees(trees):
    # 向量叉乘判断夹角
    def cross(a, b, c):
        return (b[0] - a[0]) * (c[1] - b[1]) - (c[0] - b[0]) * (b[1] - a[1])

    trees.sort()
    n = len(trees)

    if n < 4:
        return trees

    ret = [0]
    vis = [False] * n

    for i in range(1, n):
        while len(ret) > 1 and cross(trees[ret[-2]], trees[ret[-1]], trees[i]) < 0:
            vis[ret.pop()] = False
        vis[i] = True
        ret.append(i)

    m = len(ret)
    for i in range(n - 2, -1, -1):
        if not vis[i]:
            while len(ret) > m and cross(trees[ret[-2]], trees[ret[-1]], trees[i]) < 0:
                vis[ret.pop()] = False
            vis[i] = True
            ret.append(i)
    ret.pop()

    return [trees[i] for i in ret]


    # def sort(a, b):
    #     if a[0] > b[0]:
    #         return 1
    #     elif a[0] < b[0]:
    #         return -1
    #     else:
    #         if a[1] > b[1]:
    #             return 1
    #         elif a[1] < b[1]:
    #             return -1
    #         else:
    #             return 0

    # print(sorted(trees, key=functools.cmp_to_key(sort)))

    # ret = []
    #
    # trees.sort()
    # cur = 0
    # temp = []
    # for tree in trees:
    #     if tree[0] == cur:
    #         temp.append(tree)
    #     else:
    #         if len(temp) == 1:
    #             ret.append(temp[-1])
    #         elif len(temp) > 1:
    #             ret.append(temp[0])
    #             ret.append(temp[-1])
    #
    #         cur = tree[0]
    #         temp.clear()
    #         temp.append(tree)
    #
    # if len(temp) == 1:
    #     ret.append(temp[-1])
    # elif len(temp) > 1:
    #     ret.append(temp[0])
    #     ret.append(temp[-1])
    #
    # return ret


print(outerTrees([[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]))
print(outerTrees([[0,2],[1,1],[2,2],[2,4],[4,2],[3,3]]))

